package com.heima.algorithm.dynamicprogramming;

/**
 * @author 勾新杰
 * @version 1.0
 * @date 2024/11/11 15:24
 */
public class LongestCommonSubstring {

    /*
           i   t   h   e   i   m   a
       t   0   1   0   0   0   0   0
       h   0   0   2   0   0   0   0
       e   0   0   0   3   0   0   0
       m   0   0   0   0   0   1   0
       a   0   0   0   0   0   0   1

       如果某两个字符相等，就继续比较后面紧跟的两个字符是否相等，所以会有一种对角线的感觉

       if(char[i] == char[j]){
           if(i > 0 && j > 0){
               dp[i][j] = dp[i - 1][j - 1] + 1;
           }else{
               dp[i][j] = 1;
           }
       }
     */

    /**
     * 最长公共子串
     * @param str1 字符串1
     * @param str2 字符串2
     * @return 最长公共子串
     */
    public static String longestCommonSubstring(String str1, String str2) {
        int[][] dp = new int[str1.length()][str2.length()];
        int maxLength = 0;
        int beginIndex = 0;
        for (int i = 0; i < str1.length(); i++) {
            for (int j = 0; j < str2.length(); j++) {
                if (str1.charAt(i) == str2.charAt(j)){
                    if (i > 0 && j > 0) {
                        dp[i][j] = dp[i - 1][j - 1] + 1;
                        maxLength = Math.max(maxLength, dp[i][j]);
                        beginIndex = i - maxLength + 1;
                    }else {
                        dp[i][j] = 1;
                    }
                }
            }
        }
        return str1.substring(beginIndex, beginIndex + maxLength);
    }

    public static void main(String[] args) {
        String str1 = "abcde";
        String str2 = "acde";
        String result = longestCommonSubstring(str1, str2);
        System.out.println("最长公共子串为：" + result);
        str1 = "abcdef";
        str2 = "abcd";
        result = longestCommonSubstring(str1, str2);
        System.out.println("最长公共子串为：" + result);
    }
}
